

"""
1048
https://leetcode.cn/problems/longest-string-chain/

简单动态规划解法
"""
from typing import List

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=lambda x:len(x))

        d = {}  # 记录每一个单词的词链长度chain
        for word in words:
            # 每个单词首先是自身的一个单词链，所以先+1
            if word not in d:
                d[word] = 1
            
            # 按位置截掉对应位置的字符，看是否是已知的单词
            for i in range(len(word)):
                tmp_word = word[:i] + word[i+1:]
                if tmp_word in d:
                    d[word] = max(d[word], 1+d[tmp_word])
        
        longest_val = 0
        for v in d.values():
            longest_val = max(longest_val, v)
        
        return longest_val


def test():
    obj = Solution()
    res = obj.longestStrChain(["a","b","ba","bca","bda","bdca"])
    print(res)


if __name__ == "__main__":
    test()




